// File:       string.c++
// Version:    1.00
// Author:     (c) Miles Sabin, 1997
// Purpose:    approximation to ANSI C++ string class

// Change log:
//   1/01/97   v. 1.00
//  16/02/97   Replace yucky #defines with proper typedefs.
//             Renamed to basic_string_char and added typedef
//             for string.
//  21/02/97   Added stream inserters and extracters.
//             Renamed remove() to erase().
//  24/03/97   Updated traits type to Dec '96 WP spec.
//             Added swap() free fn.
//             getline() with no delim arg now uses '\n' directly
//               as per Dec '96 WP.
//  30/03/97   Moved inserter to poscmd01 and extractors to piscmd16
//               to avoid unnecessary code pull-in.
//  31/12/97   Corrected compare operation so that the length is checked if
//               the initial prefix is equal. (by Alexander Thoukydides)
//  02/02/99   Corrected find_last_of and find_last_not_of to handle the
//               pos parameter correctly.

#include "string.h"

#include <ctype.h>           // for isspace()
#include <limits.h>          // for INT_MAX
#include "algorithm.h"       // for swap()
#include "exception.h"
#include "istream.h"
#include "ostream.h"
#include "streambuf.h"


// Implementation of basic_string_char::basic_string_char_rep

basic_string_char::basic_string_char_rep::basic_string_char_rep(size_type n)
  {
    n = (n+1+3)&~3;           // add a byte for the terminator and round up to an integral number of words
    begin_ = new char[n];
    end_ = begin_;
    end_of_storage_ = begin_+n;
    ref_count_ = 1;
    *end_ = 0;
  }

inline basic_string_char::basic_string_char_rep::~basic_string_char_rep()
  { delete[] begin_; }

inline void basic_string_char::basic_string_char_rep::set_size(size_type sz)
  {
    end_ = begin_+sz;
    *end_ = 0;
  }

void basic_string_char::basic_string_char_rep::remove_reference()
  {
    if(--ref_count_ == 0)
      delete this;
  }

static basic_string_char::basic_string_char_rep* singleton = 0;

basic_string_char::basic_string_char_rep* basic_string_char::basic_string_char_rep::null_rep()
  {
    if(singleton != 0)
      return singleton->add_reference();

    singleton = new basic_string_char_rep(0);
    return singleton->add_reference();
  }


// Implementation of basic_string_char

basic_string_char::basic_string_char(basic_string_char const& s, size_type pos, size_type n)
  : rep_(basic_string_char_rep::null_rep())
  { replace(npos, 0, s, pos, n); }

basic_string_char::basic_string_char(char const* s)
  : rep_(basic_string_char_rep::null_rep())
  { replace(npos, 0, s, traits::length(s)); }

basic_string_char::basic_string_char(char const* s, size_type n)
  : rep_(basic_string_char_rep::null_rep())
  { replace(npos, 0, s, n); }

basic_string_char::basic_string_char(size_type n, char c)
  : rep_(basic_string_char_rep::null_rep())
  { replace(rep_->begin_, rep_->end_, n, c); }

basic_string_char::basic_string_char(char const* first, char const* last)
  : rep_(basic_string_char_rep::null_rep())
  { replace(npos, 0, first, last-first); }

basic_string_char::~basic_string_char()
  { rep_->remove_reference(); }

basic_string_char::const_rev_iterator basic_string_char::rbegin() const
  { return const_rev_iterator(rep_->end_); }

basic_string_char::const_rev_iterator basic_string_char::rend() const
  { return const_rev_iterator(rep_->begin_); }

basic_string_char::size_type basic_string_char::max_size() const
  { return 1<<24; }

void basic_string_char::resize(size_type n)
  { resize(n, traits::eos()); }

void basic_string_char::resize(size_type n, char c)
  {
    int change = n-size();
    if(change > 0)
      replace(rep_->end_, rep_->end_, change, c);
    else
      replace(n, npos, 0, 0);
  }

void basic_string_char::reserve(size_type sz)
  {
    if(sz <= capacity() && !rep_->is_shared())
      return;

    if(sz <= capacity())
      unshare();
    else
    {
      size_type new_capacity = capacity()*2;
      if(new_capacity < sz)
        new_capacity = sz;

      basic_string_char_rep* new_rep = new basic_string_char_rep(new_capacity);
      traits::copy(new_rep->begin_, rep_->begin_, size());
      new_rep->set_size(size());
      rep_->remove_reference();
      rep_ = new_rep;
    }
  }

basic_string_char::size_type basic_string_char::find(basic_string_char const& s, size_type pos) const
  { return find(s.data(), pos, s.size()); }

basic_string_char::size_type basic_string_char::find(char const* s, size_type pos) const
  { return find(s, pos, traits::length(s)); }

basic_string_char::size_type basic_string_char::find(char const* s, size_type pos, size_type n) const
  {
    for(size_type xpos = pos; xpos+n <= size(); ++xpos)
      if(rep_->begin_[xpos] == *s && traits::compare(data()+xpos, s, n) == 0)
        return xpos;

    return npos;
  }

basic_string_char::size_type basic_string_char::find(char c, size_type pos) const
  {
    char const* p = traits::find(data()+pos, size()-pos, c);
    return p == 0 ? npos : p-rep_->begin_;
  }

basic_string_char::size_type basic_string_char::rfind(basic_string_char const& s, size_type pos) const
  { return rfind(s.data(), pos, s.size()); }

basic_string_char::size_type basic_string_char::rfind(char const* s, size_type pos) const
  { return rfind(s, pos, traits::length(s)); }

basic_string_char::size_type basic_string_char::rfind(char const* s, size_type pos, size_type n) const
  {
    if(n > size())
      return npos;

    size_type xpos = size()-n;
    if(xpos > pos)
      xpos = pos;

    ++xpos;
    while(xpos-- > 0)
      if(rep_->begin_[xpos] == *s && traits::compare(data()+xpos, s, n) == 0)
        return xpos;

    return npos;
  }

basic_string_char::size_type basic_string_char::rfind(char c, size_type pos) const
  {
    if(empty())
      return npos;

    size_type xpos = size()-1;
    if(xpos > pos)
      xpos = pos;

    ++xpos;
    while(xpos-- > 0)
      if(rep_->begin_[xpos] == c)
        return xpos;

    return npos;
  }

basic_string_char::size_type basic_string_char::find_first_of(basic_string_char const& s, size_type pos) const
  { return find_first_of(s.data(), pos, s.size()); }

basic_string_char::size_type basic_string_char::find_first_of(char const* s, size_type pos) const
  { return find_first_of(s, pos, traits::length(s)); }

basic_string_char::size_type basic_string_char::find_first_of(char const* s, size_type pos, size_type n) const
  {
    for(size_type xpos = pos; xpos < size(); ++xpos)
      if(traits::find(s, n, rep_->begin_[xpos]) != 0)
        return xpos;

    return npos;
  }

basic_string_char::size_type basic_string_char::find_first_of(char c, size_type pos) const
  { return find(c, pos); }

basic_string_char::size_type basic_string_char::find_last_of(basic_string_char const& s, size_type pos) const
  { return find_last_of(s.data(), pos, s.size()); }

basic_string_char::size_type basic_string_char::find_last_of(char const* s, size_type pos) const
  { return find_last_of(s, pos, traits::length(s)); }

basic_string_char::size_type basic_string_char::find_last_of(char const* s, size_type pos, size_type n) const
  {
    for(size_type xpos = pos == npos ? size() : pos + 1; xpos-- > 0;)
      if(traits::find(s, n, rep_->begin_[xpos]) != 0)
        return xpos;

    return npos;
  }

basic_string_char::size_type basic_string_char::find_last_of(char c, size_type pos) const
  { return rfind(c, pos); }

basic_string_char::size_type basic_string_char::find_first_not_of(basic_string_char const& s, size_type pos) const
  { return find_first_not_of(s.data(), pos, s.size()); }

basic_string_char::size_type basic_string_char::find_first_not_of(char const* s, size_type pos) const
  { return find_first_not_of(s, pos, traits::length(s)); }

basic_string_char::size_type basic_string_char::find_first_not_of(char const* s, size_type pos, size_type n) const
  {
    for(size_type xpos = pos; xpos < size(); ++xpos)
      if(traits::find(s, n,  rep_->begin_[xpos]) == 0)
        return xpos;

    return npos;
  }

basic_string_char::size_type basic_string_char::find_first_not_of(char c, size_type pos) const
  {
    for (size_type xpos = pos; xpos < size(); ++xpos)
      if(rep_->begin_[xpos] != c)
        return xpos;

    return npos;
  }

basic_string_char::size_type basic_string_char::find_last_not_of(basic_string_char const& s, size_type pos) const
  { return find_last_not_of(s.data(), pos, s.size()); }

basic_string_char::size_type basic_string_char::find_last_not_of(char const* s, size_type pos) const
  { return find_last_not_of(s, pos, traits::length(s)); }

basic_string_char::size_type basic_string_char::find_last_not_of(char const* s, size_type pos, size_type n) const
  {
    for(size_type xpos = pos == npos ? size() : pos + 1; xpos-- > 0;)
      if(traits::find(s, n, rep_->begin_[xpos]) == 0)
        return xpos;

    return npos;
  }

basic_string_char::size_type basic_string_char::find_last_not_of(char c, size_type pos) const
  {
    for(size_type xpos = pos == npos ? size() : pos + 1; xpos-- > 0;)
      if(rep_->begin_[xpos] != c)
        return xpos;

    return npos;
  }

basic_string_char basic_string_char::substr(size_type pos, size_type n) const
  { return basic_string_char(*this, pos, n); }

int basic_string_char::compare(const basic_string_char& str) const
  {
    size_type n1 = size();
    size_type n2 = str.size();
    int ans = traits::compare(data(), str.data(), n1 < n2 ? n1 : n2);
    return ans != 0 ? ans : n1 < n2 ? -1 : n1 == n2 ? 0 : +1;
  }

int basic_string_char::compare(size_type pos1, size_type n1, const basic_string_char& str) const
  {
    if (size() < pos1 + n1)
      n1 = size() - pos1;
    size_type n2 = str.size();
    int ans = traits::compare(data()+pos1, str.data(), n1 < n2 ? n1 : n2);
    return ans != 0 ? ans : n1 < n2 ? -1 : n1 == n2 ? 0 : +1;
  }

int basic_string_char::compare(size_type pos1, size_type n1, const basic_string_char& str, size_type pos2, size_type n2) const
  {
    if (size() < pos1 + n1)
      n1 = size() - pos1;
    if (str.size() < pos2 + n2)
      n2 = str.size() - pos2;
    int ans = traits::compare(data()+pos1, str.data()+pos2, n1 < n2 ? n1 : n2);
    return ans != 0 ? ans : n1 < n2 ? -1 : n1 == n2 ? 0 : +1;
  }

int basic_string_char::compare(const char* s) const
  {
    size_type n1 = size();
    size_type n2 = traits::length(s);
    int ans = traits::compare(data(), s, n1 < n2 ? n1 : n2);
    return ans != 0 ? ans : n1 < n2 ? -1 : n1 == n2 ? 0 : +1;
  }

int basic_string_char::compare(size_type pos1, size_type n1, const char* s, size_type n2) const
  {
    if (size() < pos1 + n1)
      n1 = size() - pos1;
    if (traits::length(s) < n2)
      n2 = traits::length(s);
    int ans = traits::compare(data()+pos1, s, n1 < n2 ? n1 : n2);
    return ans != 0 ? ans : n1 < n2 ? -1 : n1 == n2 ? 0 : +1;
  }

basic_string_char& basic_string_char::operator=(basic_string_char const& rhs)
  {
    rhs.rep_->add_reference();
    rep_->remove_reference();
    rep_ = rhs.rep_;
    return *this;
  }

basic_string_char& basic_string_char::operator=(char const* rhs)
  { return replace(0, npos, rhs, traits::length(rhs)); }

basic_string_char& basic_string_char::operator=(char rhs)
  { return replace(0, npos, &rhs, 1); }

basic_string_char::rev_iterator basic_string_char::rbegin()
  {
    if(rep_->is_shared())
      unshare();
    return rev_iterator(rep_->end_);
  }

basic_string_char::rev_iterator basic_string_char::rend()
  {
    if(rep_->is_shared())
      unshare();
    return rev_iterator(rep_->begin_);
  }

basic_string_char& basic_string_char::operator+=(basic_string_char const& rhs)
  { return replace(npos, 0, rhs, 0, rhs.size()); }

basic_string_char& basic_string_char::operator+=(char const* rhs)
  { return replace(npos, 0, rhs, traits::length(rhs)); }

basic_string_char& basic_string_char::operator+=(char rhs)
  { return replace(npos, 0, &rhs, 1); }

basic_string_char& basic_string_char::append(basic_string_char const& s, size_type pos, size_type n)
  { return replace(npos, 0, s, pos, n); }

basic_string_char& basic_string_char::append(char const* s)
  { return replace(npos, 0, s, traits::length(s)); }

basic_string_char& basic_string_char::append(char const* s, size_type n)
  { return replace(npos, 0, s, n); }

basic_string_char& basic_string_char::append(size_type n, char c)
  { return replace(rep_->end_, rep_->end_, n, c); }

basic_string_char& basic_string_char::append(char const* first, char const* last)
  { return replace(npos, 0, first, last-first); }

basic_string_char& basic_string_char::assign(basic_string_char const& s, size_type pos, size_type n)
  { return replace(0, npos, s, pos, n); }

basic_string_char& basic_string_char::assign(char const* s)
  { return replace(0, npos, s, traits::length(s)); }

basic_string_char& basic_string_char::assign(char const* s, size_type n)
  { return replace(0, npos, s, n); }

basic_string_char& basic_string_char::assign(size_type n, char c)
  { return replace(rep_->begin_, rep_->end_, n, c); }

basic_string_char& basic_string_char::assign(char const* first, char const* last)
  { return replace(0, npos, first, last-first); }

basic_string_char& basic_string_char::insert(size_type pos1, basic_string_char const& s, size_type pos2, size_type n)
  { return replace(pos1, 0, s, pos2, n); }

basic_string_char& basic_string_char::insert(size_type pos, char const* s)
  { return replace(pos, 0, s, traits::length(s)); }

basic_string_char& basic_string_char::insert(size_type pos, char const* s, size_type n)
  { return replace(pos, 0, s, n); }

basic_string_char& basic_string_char::insert(size_type pos, size_type n, char c)
  { return replace(rep_->begin_+pos, rep_->begin_+pos, n, c); }

basic_string_char::iterator basic_string_char::insert(iterator p, char c)
  {
    size_type pos = p-rep_->begin_;
    replace(p, p, 1, c);
    return rep_->begin_+pos;
  }

basic_string_char::iterator basic_string_char::insert(iterator p, size_type n, char c)
  {
    size_type pos = p-rep_->begin_;
    replace(p, p, n, c);
    return rep_->begin_+pos;
  }

void basic_string_char::insert(iterator p, char const* first, char const* last)
  { replace(p-rep_->begin_, 0, first, last-first); }

basic_string_char& basic_string_char::erase(size_type pos, size_type n)
  { return replace(pos, n, 0, 0); }

basic_string_char& basic_string_char::erase(iterator pos)
  { return replace(pos, pos+1, 0, size_type(0)); }

basic_string_char& basic_string_char::erase(iterator first, iterator last)
  { return replace(first-rep_->begin_, last-first, 0, size_type(0)); }

basic_string_char::iterator basic_string_char::replace_aux(size_type pos, size_type xlen, size_type n)
  {
    if(pos > size())
      pos = size();

    iterator p = rep_->begin_+pos;

    int delta = int(n)-xlen;
    size_type new_size = size()+delta;

    if(!rep_->is_shared() && capacity() >= new_size)
    {
      if(delta != 0)
        traits::move(p+xlen+delta, p+xlen, size()-(pos+xlen));
      rep_->set_size(new_size);
    }
    else
    {
      int new_capacity = capacity();
      if(capacity() < new_size)
      {
        new_capacity *= 2;

        if(new_capacity < new_size)
          new_capacity = new_size;
      }

      basic_string_char_rep* new_rep = new basic_string_char_rep(new_capacity);
      iterator np = new_rep->begin_+pos;
      traits::copy(new_rep->begin_, rep_->begin_, pos);
      traits::copy(np+xlen+delta, p+xlen, size()-(pos+xlen));
      new_rep->set_size(new_size);
      p = np;

      rep_->remove_reference();
      rep_ = new_rep;
    }

    return p;
  }

basic_string_char& basic_string_char::replace(size_type pos1, size_type n1, basic_string_char const& s, size_type pos2, size_type n2)
  {
    size_type rlen = s.size()-pos2;
    if(rlen > n2)
      rlen = n2;
    return replace(pos1, n1, s.rep_->begin_+pos2, rlen);
  }

basic_string_char& basic_string_char::replace(size_type pos, size_type n1, char const* s)
  { return replace(pos, n1, s, traits::length(s)); }

basic_string_char& basic_string_char::replace(size_type pos, size_type n, char c)
  { return replace(rep_->begin_+pos, rep_->begin_+pos, c, n); }

basic_string_char& basic_string_char::replace(iterator i1, iterator i2, basic_string_char const& str)
  { return replace(i1-rep_->begin_, i2-i1, str); }

basic_string_char& basic_string_char::replace(iterator i1, iterator i2, char const* s, size_type n)
  { return replace(i1-rep_->begin_, i2-i1, s, n); }

basic_string_char& basic_string_char::replace(iterator i1, iterator i2, char const* s)
  { return replace(i1-rep_->begin_, i2-i1, s, traits::length(s)); }

basic_string_char& basic_string_char::replace(iterator i1, iterator i2, char const* j1, char const* j2)
  { return replace(i1-rep_->begin_, i2-i1, j1, j2-j1); }

basic_string_char& basic_string_char::replace(iterator i1, iterator i2, size_type n, char c)
  {
    traits::assign(replace_aux(i1-rep_->begin_, i2-i1, n), n, c);
    return *this;
  }

basic_string_char& basic_string_char::replace(size_type pos, size_type n1, char const* s, size_type n2)
  {
    size_type xlen = size()-pos;
    if(xlen > n1)
      xlen = n1;
    traits::copy(replace_aux(pos, xlen, n2), s, n2);
    return *this;
  }

basic_string_char::size_type basic_string_char::copy(char* s, size_type n, size_type pos)
  {
    size_type rlen = size()-pos;
    if(rlen > n)
      rlen = n;
    traits::copy(s, rep_->begin_+pos, rlen);
    return rlen;
  }

void basic_string_char::swap(basic_string_char& x)
  { ::swap(rep_, x.rep_); }

void basic_string_char::unshare()
  {
    if(!rep_->is_shared())
      return;

    basic_string_char_rep* new_rep = new basic_string_char_rep(size());
    traits::copy(new_rep->begin_, rep_->begin_, size());
    new_rep->set_size(size());

    rep_->remove_reference();
    rep_ = new_rep;
  }


// Implementation of basic_string_char free fns

basic_string_char operator+(basic_string_char const& lhs, basic_string_char const& rhs)
{
  return basic_string_char(lhs).append(rhs);
}

basic_string_char operator+(char const* lhs, basic_string_char const& rhs)
{
  return basic_string_char(lhs).append(rhs);
}

basic_string_char operator+(basic_string_char const& lhs, char const* rhs)
{
  return basic_string_char(lhs).append(rhs);
}

basic_string_char operator+(char lhs, basic_string_char const& rhs)
{
  return basic_string_char(1, lhs).append(rhs);
}

basic_string_char operator+(basic_string_char const& lhs, char rhs)
{
  return basic_string_char(lhs).append(1, rhs);
}
